package com.datastructure.linkedlist;

/**
 * 用java语言实现链表
 *
 * @author luhd
 * @date 2022-11-01
 */
public class LinkList<T> {

    // 节点定义
    private class Node {
        // 数据
        T item;
        // 下一个节点
        Node next;

        // 构造器
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }

        public Node(T item) {
            this.item = item;
        }
    }

    // 头节点
    private Node head;
    // 尾节点
    private Node tail;
    // 节点个数
    private int size;

    /**
     * 链表定义
     */
    public LinkList() {
        this.head = new Node(null, null);
        size = 0;
    }

    /**
     * 查找特定位置的链表节点
     */
    public Node get(int index) {
        if (index < 0 || index >= this.size) {
            return null;
        } else {
            Node temp = this.head;
            for (int i = 1; i <= index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    }

    /**
     * 链表尾部添加数据
     */
    public void add(T data) {
        Node temp = new Node(data);
        // 链表为空时
        if (this.size == 0) {
            head = temp;
            tail = head;
        } else {
            Node last = tail;
            last.next = temp;
            this.tail = temp;
        }
        this.size++;
    }

    /**
     * 插入链表节点
     */
    public void insert(int index, T data) throws Exception {
        if (index < 0 || index > this.size) {
            throw new Exception("插入超出范围");
        } else {
            // 初始化当前插入的节点
            Node newNode = new Node(data);
            if (index == 0) {
                if (this.size > 0) {
                    Node temp = head;
                    newNode.next = temp;
                }
                head = newNode;
            } else if (index == this.size) {
                // 在尾节点插入元素
                Node temp = tail;
                temp.next = newNode;
                this.tail = newNode;
            } else {
                // 在中间插入元素
                Node preNode = get(index - 1);
                Node nextNode = preNode.next;
                preNode.next = newNode;
                newNode.next = nextNode;
            }
        }
        this.size++;

        if (size == 1) {
            tail = head;
        }
    }

    /**
     * 删除节点
     */
    public void del(int index) throws Exception {
        if (index < 0 || index >= this.size) {
            throw new Exception("删除超出范围");
        } else {
            // 删除头节点
            if (index == 0) {
                Node temp = this.head.next;
                this.head = temp;
            } else if (index == this.size - 1) {
                // 删除尾节点
                Node preNode = get(index - 1);
                preNode.next = null;
                this.tail = preNode;
            } else {
                // 删除中间节点
                Node preNode = get(index - 1);
                Node nextNode = preNode.next.next;
                preNode.next = nextNode;
            }
        }
        this.size--;
    }

    /**
     * 移除末尾元素
     */
    public T remove() throws Exception {
        if (this.size == 0) {
            throw new Exception("链表为空，无法移除");
        }
        // 只有一个元素
        if (this.size == 1) {
            T data = this.head.item;
            this.head = null;
            this.tail = null;
            this.size--;
            return data;
        } else {
            Node preNode = get(this.size - 2);
            T data = this.tail.item;
            preNode.next = null;
            this.tail = preNode;
            this.size--;
            return data;
        }
    }

    /**
     * 删除特定元素的第一个位置
     */
    public boolean deleteData(T data) {
        boolean flag = false;
        if (this.size == 0) {
            return flag;
        } else {
            Node curNode = this.head;
            // 元素位于第一个节点
            if (curNode.item == data) {
                Node nextNode = curNode.next;
                this.head = nextNode;
                flag = true;
                // 当前列表只有一个节点
                if (this.size == 1) {
                    tail = head;
                }
                this.size --;
            } else {
                while(curNode != null) {
                    Node nextNode = curNode.next;
                    if (curNode != null && curNode.item == data) {
                        // 删除元素为尾节点
                        if (nextNode.next == null) {
                            this.tail = curNode;
                            curNode.next = null;
                        } else {
                            // 删除节点为中间节点
                            Node temp = curNode.next.next;
                            curNode.next = temp;
                        }
                        flag = true;
                        this.size --;
                        break;
                    }
                   curNode = curNode.next;
                }
            }
        }
        return flag;
    }

    /**
     * 输出当前整个链表数据
     */
    public void printLinkList() {
        if (this.size == 0) {
            System.out.println("链表为空");
        } else {
            Node temp = head;
            System.out.print("目前的列表，头结点：" + head.item + ",尾结点:" + tail.item + ",整体：");
            while (temp != null) {
                System.out.print(temp.item + ",");
                temp = temp.next;
            }
            System.out.println();
        }
    }

    /**
     * 测试demo
     */
    public static void main(String args[]) throws Exception {
        LinkList linkList = new LinkList();
        linkList.add("2");
        linkList.del(0);
        linkList.printLinkList();
        linkList.insert(0, "a");
        System.out.println("删除的元素为：" + linkList.remove());
        linkList.insert(0, "2");
        linkList.insert(1, "3");
        linkList.add("3");
        linkList.printLinkList();
        linkList.del(1);
        linkList.printLinkList();
        linkList.insert(1, "1");

        linkList.insert(0, "0");
        linkList.insert(2, "0");
        linkList.del(2);
        linkList.printLinkList();
        linkList.deleteData(3);
        linkList.printLinkList();
    }
}